Communication networks can facilitate point-to-point telephony between network endpoints. However, even in an age of widely available communication capability, including wireless communication networks, a phone call may not be answered. For example, the target device may be disconnected from a communication network, either because the device is out of range of the communication network, or because the device is turned off, and thus the target device does not signal the incoming call to a user. In addition, a user may choose not to answer an incoming call. In such cases, many communication networks provide the initiator of the call an opportunity to leave a recorded voice message for the user of the target device. Typically, a recorded voice message left by a caller is received at a processing node in the communication network (one example of which is a messaging node, such as a voice mail server). Based on the received voice message, a message notification can be sent to the target device that a message has been received for the target device.